Important Note:
This information is now rather out of date. My research notes are now kept on a wiki, a static version of which is located here.
Overview of Artificial Intelligence Algorithms for Planning
This page catalogs some of the fundamental algorithms in AI planning, both general and path. The intent is that with a strong understanding of the techniques used, we will be better able to provide support for the system programmer.
Path Planning
These algorithms deal specifically with the task of how to best move through an environment.
A*
A* is perhaps one of the simplest and most straight forward path planning algorithms, and is both fast and optimal. The algorithm requires an "admissible heuristic" to generate a cost estimate from the current location to the goal. To be admissible, the heuristic must never over-estimate the distance. In typical path finding algorithms, this is the straight line distance to the goal.
The standard A* algorithm requires that the environment be discretized appropriately. The algorithm is essentially a graph traversal, with each node representing a location, and each node is connected to each of its immediate neighbors (locations that can be reached with one move by the agent). As one can imagine, how the discretization of the world is done can have great impacts: too coarse and the representation is inaccurate, too fine and the search time increases greatly.
A* can be used for any graph traversal problem (and is superior to Dijkstra's Algorithm when an admissible heuristic is available). Williams and Ragno (whose work I cover on my research page) extended the algorithm to avoid nodes which share "conflicts" with previously expanded nodes. In their work, the graph represents possible failure states and the admissible heuristic is that the components are in working order. The conflicts are discrepencies between the predicted outputs and the observed outputs of the system.
- P.E. Hart, N.J. Nilsson, and B. Raphael. A Formal Basis for the Heuristic Determination of Minimum Cost Paths. Systems Science and Cybernetics, IEEE Transactions on, 4(2):100-107, July 1968.
- Brian C. Williams and Robert J. Ragno. Conflict-directed A* and Its Role in Model-based Embedded Systems. Discrete Applied Mathematics, 155(12):1562-1595, 2007. SAT 2001, the Fourth International Symposium on the Theory and Applications of Satisfiability Testing.
D*
Dynamic A* (often referred to as D*) is a variation of A* that is intended to provide for faster re-planning times. This is useful when there are unknown obstacles in the environment. A* would typically handle this situation by simply restarting, but D* takes advantage of previously computed paths to speed up the process.
Unlike A*, D* begins with the goal node and works backwards to the robot. As obstacles are discovered (most likely close to the robot due to their limited sensor range), affected nodes are reevaluted and marked as RAISE since their esitmated cost may have been increased by the discovery of the obstacle. These RAISE nodes are then evaluted: first a check is made to see if a neighbor can lower their cost (avoiding the obstacle). If not, the neighboring nodes are also marked RAISE. LOWER nodes are also propogated in a similar fashion.
Focused D* is a natural extension that directs the waves of propogating RAISE and LOWER nodes towards the robot, reducing the number of nodes to evaluate.
- A. Stentz. Optimal and Efficient Path Planning for Unknown and Dynamic Environments. Technical report, DTIC Document, 1993.
- A. Stentz. The Focussed D* Algorithm for Real-time Replanning. In International Joint Conference on Artificial Intelligence, volume 14, pages 1652-1659. Citeseer, 1995.
RRT
A Rapidly exploring Random Tree is well suited to continuous domains with high dimensionality. This means that the algorithm is suitable for real world applications such as driving a car, which has moment and dynamic limitations of the ways in which it can turn (cutting the wheel 90 degrees while travelling at 100 mph is generally inadvisable). While not optimal, it is fast.
- S.M. LaValle. Rapidly-exploring Random Trees: A New Tool for Path Planning. In, (98-11), 1998.
- J. Bruce and M. Veloso. Real-time Randomized Path Planning for Robot Navigation. In Intelligent Robots and Systems, 2002. IEEE/RSJ International Conference on, volume 3, pages 2383-2388. Ieee, 2002.
- J.J. Kuffner Jr and S.M. LaValle. RRT-Connect: An Efficient Approach to Single-query Path Planning. In Robotics and Automation, 2000. Proceedings. ICRA'00. IEEE International Conference on, volume 2, pages 995-1001. IEEE, 2000.
General Planning
By Proof
Graphplan
Huzzah! A description of Graphplan.
- A.L. Blum and M.L. Furst. Fast Planning Through Planning Graph Analysis* 1. Artificial intelligence, 90(1-2):281-300, 1997.
- S. Kambhampati, E. Parker, and E. Lambrecht. Understanding and Extending Graphplan. Recent Advances in AI Planning, pages 260-272, 1997.
SAT Plan
Planning for Multiple Agents
When planning must be done to coordinate multiple robots to work together, a whole new set of problems arise. While one could used an algorithm designed for a single agent by treating the separate agents as one giant agent with added restrictions to avoid collisions and such, this causes the solution space to grow rapidly and is cumbersome. Specific multi-agent algorithms are designed to solve these problems.
